class Solution {
public:

    bool nextPermutation(vector<int> &num) {
        int n = num.size();
        int i = n - 1;

        for (; i > 0; --i) {
            if (num[i] > num[i - 1]) {
                break;
            }
        }
        if (i == 0) {
            return false;
        }
        int j = n - 1;
        while (num[j] <= num[i - 1]) {
            --j;
        }
        swap(num[i - 1], num[j]);
        reverse(num.begin() + i, num.end());
        return true;
    }

    vector<vector<int> > permuteUnique(vector<int> &num) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vector<vector<int> > ans;
        sort(num.begin(), num.end());

        while (true) {
            ans.push_back(num);
            if (!nextPermutation(num)) {
                break;
            }
        }
        return ans;
    }

};
